package com.ljy.my_study.lintcode.最小子串覆盖;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author James
 * @date 2018年10月12日
 */
public class TestMain {
	// 描述
	// 给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子串。
	//
	// If there is no such window in source that covers all characters in target,
	// return the emtpy string "".
	// If there are multiple such windows, you are guaranteed that there will always
	// be only one unique minimum window in source.
	// The target string may contain duplicate characters, the minimum window should
	// cover all characters including the duplicate characters in target.
	//
	// 您在真实的面试中是否遇到过这个题？
	// 说明
	// Should the characters in minimum window has the same order in target?
	//
	// Not necessary.
	// 样例
	// 给出source = "ADOBECODEBANC"，target = "ABC" 满足要求的解 "BANC"
	public static void main(String[] args) {
//		String source="aaaaaaaaaaaabbbbbcdd";
//		String target="abcdd";
//		String source="aaaaaaaaaaaaaaaaaaabbbbbbbbbdfadsfjalsdjfalsdjfsadfadf";
//		String target="aaaaaabbbbbbbbbdfjaldjf";
		String source="ja;jfadflakjdfa;djfadfdnvadbfkbH:DADHFLDSHfakldhflakdf;adfasdhfaufhakdbalbgaldbalkdfafhalkdsfhalsdufhakldbakladshfuojfanjoiehflakshf";
		String target="adfanbajfasdjfaodjfaldfnasldfjao";
//		List<Character> list=new ArrayList<>();
//		char[] charArr=target.toCharArray();
//		for(int i=0;i<charArr.length;i++) {
//			list.add(charArr[i]);
//		}
//		list.remove(new Character('C'));
//		list.remove(new Character('C'));
//		System.out.println(list);
		System.out.println(minWindow(source,target));
	}

	public static String minWindow(String source, String target) {
		if(source==null||target==null) {
			return null;
		}
		if("".equals(source)||"".equals(target)) {
			return "";
		}
		List<Node> eList=new ArrayList<>();	
		StringBuilder sb=new StringBuilder();
		List<Character> list=new ArrayList<>();
		char[] charArr=target.toCharArray();
		for(int i=0;i<charArr.length;i++) {
			list.add(charArr[i]);
		}
		List<Character> newList=new ArrayList<>(Arrays.asList(new Character[list.size()]));
		Collections.copy(newList, list);
		char[] sourceCharArr=source.toCharArray();
		for(int i=0;i<sourceCharArr.length;i++) {
			if(!list.contains(sourceCharArr[i])&&sb.length()==0)continue;
			eList.add(new Node(sourceCharArr[i],i));
		}
		if(eList.size()<list.size())return "";
		if(list.size()==1) {
			return eList.get(0).getC()+"";
		}
		String result=null;
		for(int i=0;i<=eList.size()-charArr.length;i++) {
			newList=new ArrayList<>(Arrays.asList(new Character[list.size()]));
			Collections.copy(newList, list);
			int start=0;
			int end=0;
			for(int j=i;j<eList.size();j++) {
				if(end-start>0&&(j-i)>(end-start)) {
					break;
				}
				Node n=eList.get(j);
				newList.remove(n.getC());
				if(newList.size()==0) {
					newList=new ArrayList<>(Arrays.asList(new Character[list.size()]));
					Collections.copy(newList, list);
					if(end-start>0&&(j-i)<(end-start)) {
						start=eList.get(i).getIndex();
						end=eList.get(j).getIndex()+1;
					}else if(end-start==0&&(j-i)>0) {
						start=eList.get(i).getIndex();
						end=eList.get(j).getIndex()+1;
					}
					break;
				}
			}
			if((result==null)||(result!=null&&end!=start&&(end-start)>=list.size()&&(end-start)<result.length())) {
				result=source.substring(start,end);
			}else {
				
			}
		}
		return result;
	}
	
	public static class Node{
		private Character c;
		private Integer index;
		
		public Node(Character c, Integer index) {
			super();
			this.c = c;
			this.index = index;
		}
		public Character getC() {
			return c;
		}
		public void setC(Character c) {
			this.c = c;
		}
		public Integer getIndex() {
			return index;
		}
		public void setIndex(Integer index) {
			this.index = index;
		}
		@Override
		public String toString() {
			return "{\"c\":\"" + c + "\",\"index\":\"" + index + "\"} ";
		}
		
	}
}
